package 算法.其他算法;

/**
 * 保证奇数和奇数，偶数和偶数之间的相对位置不变。
 */
public class JZ21调整数组顺序使奇数位于偶数前面1 {
    //双指针
    public int[] reOrderArray (int[] array) {
        int n = array.length;
        int[] res = new int[n];
        //统计奇数个数
        int odd = 0;
        //遍历统计
        for(int i = 0; i < n; i++){
            if(array[i] % 2 == 1)
                odd++;
        }
        //x与y分别表示答案中奇偶数的坐标
        int x = 0, y = odd;
        for(int i = 0; i < n; i++){
            //奇数在前
            if(array[i] % 2 == 1){
                res[x] = array[i];
                x++;
                //偶数在后
            }else{
                res[y] = array[i];
                y++;
            }
        }
        return  res;
    }

    //在原数组上修改
    public int[] reOrderArray2 (int[] array) {
        int i = 0;
        for (int j=0; j < array.length; j++) {
            // 遇到奇数时
            if (array[j] % 2 == 1) {
                // 先将 array[j] 赋值
                int tmp = array[j];
                // 将 【i, j-1】数组后移动
                for (int k=j-1; k>=i; --k) {
                    array[k+1] = array[k];
                }
                // 将array[j]插入到 i++ 的位置
                array[i++] = tmp;
            }
        }
        return array;
    }
}
